\documentclass[E:/GsjzTle/main/main.tex]{subfiles}
\begin{document}

给定一个空序列，有 \(N\) 次操作，每次向序列末尾插入
\(L , L+1,L+2,...R\)\\
求每次操作结束后序列的中位数

区间离散化（左闭右开）+ 权值线段树（线段树空间要开八倍）

\begin{lstlisting}
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 4e5 + 10;
ll x[N], y[N];
struct Tree
{
	int l, r;
	ll sum, len, lazy;
} tree[N << 3];
int b[N << 1];
void pushup(int rt)
{
	tree[rt].sum = tree[rt << 1].sum + tree[rt << 1 | 1].sum;
}
void build(int l, int r, int rt)
{
	tree[rt].l = l;
	tree[rt].r = r;
	tree[rt].sum = tree[rt].lazy = 0;
	if(l == r)
	{
		tree[rt].len = b[l + 1] - b[l];
		return;
	}
	int mid = l + r >> 1;
	build(l, mid, rt << 1);
	build(mid + 1, r, rt << 1 | 1);
	tree[rt].len = tree[rt << 1].len + tree[rt << 1 | 1].len;
}
void pushdown(int rt)
{
	if(tree[rt].lazy != 0)
	{
		tree[rt << 1].lazy += tree[rt].lazy;
		tree[rt << 1].sum  += tree[rt].lazy * tree[rt << 1].len;
		tree[rt << 1 | 1].lazy += tree[rt].lazy;
		tree[rt << 1 | 1].sum  += tree[rt].lazy * tree[rt << 1 | 1].len;
		tree[rt].lazy = 0;
	}
}
void update(int rt, int l, int r)
{
	if(l <= tree[rt].l && tree[rt].r <= r)
	{
		tree[rt].sum += tree[rt].len ;
		tree[rt].lazy ++;
		return ;
	}
	pushdown(rt);
	int mid = tree[rt].l + tree[rt].r >> 1;
	if(l <= mid) update(rt << 1, l, r);
	if(mid < r) update(rt << 1 | 1, l, r);
	pushup(rt);
}
int query(int rt, ll K)
{
	if(tree[rt].l == tree[rt].r)
	{
		ll tmp = tree[rt].sum / tree[rt].len;
		return b[tree[rt].l] + (K - 1) / tmp;
	}
	pushdown(rt);
	if(K <= tree[rt << 1].sum) return query(rt << 1, K);
	else return query(rt << 1 | 1, K - tree[rt << 1].sum);
}
signed main()
{
	ios::sync_with_stdio(false); 
	cin.tie(0) , cout.tie(0);
	int n, a1, a2, b1, b2, c1, c2, m1, m2;
	cin >> n;
	cin >> x[1] >> x[2] >> a1 >> b1 >> c1 >> m1;
	cin >> y[1] >> y[2] >> a2 >> b2 >> c2 >> m2;
	for(int i = 3; i <= n; i++)
	{
		x[i] = (1ll * a1 * x[i - 1] + 1ll * b1 * x[i - 2] + c1) % m1;
		y[i] = (1ll * a2 * y[i - 1] + 1ll * b2 * y[i - 2] + c2) % m2;
		// 题目的奇葩求 [L,R] 方法
	}
	int len = 0;
	for(int i = 1; i <= n; i++)
	{
		ll l, r;
		l = min(x[i], y[i]) + 1;
		r = max(x[i], y[i]) + 1;
		x[i] = l;
		y[i] = r;
		b[++len] = l;
		b[++len] = r + 1;
	}
	sort(b + 1, b + len + 1);
	len = unique(b + 1, b + len + 1) - (b + 1);
	for(int i = 1; i <= n; i++)
	{
		x[i] = lower_bound(b + 1, b + len + 1, x[i]) - b;
		y[i] = lower_bound(b + 1, b + len + 1, y[i] + 1) - b;
	}
	build(1, len - 1, 1);
	ll sum = 0;
	for(int i = 1; i <= n; i++)
	{
		update(1, x[i], y[i] - 1);
		sum += b[y[i]] - b[x[i]];
		cout << query(1 , (sum + 1) / 2) << '\n';
	}
	return 0;
}
\end{lstlisting}

\end{document}
